package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/snapshot-array/'>快照数组(Snapshot Array)</a>
 * <p>
 * 实现支持下列接口的「快照数组」- SnapshotArray：
 *     <ul>
 *         <li>SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。</li>
 *         <li>void set(index, val) - 会将指定索引 index 处的元素设置为 val。</li>
 *         <li>int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。</li>
 *         <li>int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。</li>
 *     </ul>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例1：
 *      输入：["SnapshotArray","set","snap","set","get"]
 *              [[3],[0,5],[],[0,6],[0,0]]
 *      输出：[null,null,0,null,5]
 *      解释：
 *          SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
 *          snapshotArr.set(0,5);  // 令 array[0] = 5
 *          snapshotArr.snap();  // 获取快照，返回 snap_id = 0
 *          snapshotArr.set(0,6);
 *          snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= length <= 50000</li>
 *     <li>题目最多进行50000 次set，snap，和 get的调用 。</li>
 *     <li>0 <= index < length</li>
 *     <li>0 <= snap_id < 我们调用 snap() 的总次数</li>
 *     <li>0 <= val <= 10^9</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/4/26 9:26
 */
public class LC1146SnapshotArray_M {
    static class SnapshotArray {

        private int snapId = 0;
        /**
         * 用于记录每个 index 的历史修改记录纸。<br>
         * 例如： set(index,val)。key为index的记录，将会增加一条int[]，其中0下标的值为currSnapId，1下标对应的值为val
         */
        private final Map<Integer, List<int[]>> history;

        public SnapshotArray(int length) {
            history = new HashMap<>(length);
        }

        public void set(int index, int val) {
            history.computeIfAbsent(index, v -> new ArrayList<>()).add(new int[]{snapId, val});
        }

        public int snap() {
            return snapId++;
        }

        public int get(int index, int snap_id) {
            if (!history.containsKey(index)) {
                return 0;
            }
            List<int[]> h = history.get(index);
            int x = binarySearch(h, snap_id);
            return x < 0 ? 0 : h.get(x)[1];
        }

        /**
         * // 返回最大的下标 i，满足 h[i][0] <= x；不存在则返回 -1
         */
        private int binarySearch(List<int[]> h, int snap_id) {
            // 开区间 (left, right)
            int left = -1;
            int right = h.size();
            while (left + 1 < right) {
                int mid = left + ((right - left) >> 1);
                // 查询到符合条件的：区间缩小为 (mid, right)
                if (h.get(mid)[0] <= snap_id) {
                    left = mid;
                }
                // 未查询到符合条件的：区间缩小为 (left, mid)
                else {
                    right = mid;
                }
            }
            return left;
        }
    }


    public static void main(String[] args) {
        SnapshotArray obj = new SnapshotArray(3);
        obj.set(0, 5);
        System.out.println(obj.snap());
        obj.set(0, 6);
        System.out.println(obj.get(0, 0));
    }
}
